This invention belongs to the field of steganography, the science of information hiding. Sending an encrypted message over a public channel gives a clear idea to anybody who intercepts the message that secret communication is occurring. There are cases when it is desirable to hide the very presence of communication while keeping a certain degree of security.
Historically, many steganographic techniques have been designed. Invisible ink, use of clear chemicals that change color when exposed to heat or other chemicals, microdots, and many other techniques have been used in the past. Today, various forms of digitized information, such as digital images, videos, or soundtracks provide a natural environment for hiding secret messages. Specifically, the noise component of such digital information is especially attractive for the aforementioned purpose.
One of the most common steganographic techniques for secret hiding of messages in digital images is called the Least Significant Bit (LSB) encoding. In this technique, a secret message is encoded into the least significant bit of some image. This naive scheme, however, has some obvious drawbacks. Anybody can look at the least significant bit of the image to determine whether a message exists. Second, if one byte is used for representing the color of one pixel (for example, this is true in grayscale images), the secret message can form at most 12.5% of the image size.
In the present invention, a method is provided which uses three-dimensional chaotic maps to encrypt a secret message, which is then embedded into the least two significant bits of the pixel values of some carrier image. The use of three-dimensional chaotic maps is described in copending, U.S. patent application, Ser. No. 08/763,572, filed Dec. 10, 1996, for "METHOD FOR ENCRYPTING AND DECRYPTING DATA USING CHAOTIC MAPS", hereby incorporated by reference. During the embedding process, the carrier image is slightly modified so that the modifications resemble a Gaussian noise invisible to the human eye even under close inspection. The encryption has two functions: it provides security (anybody without the key will be unable to recover the secret message); and, also, the encrypted message is randomized by the encryption. After embedding, it does not create any patterns in the least two significant bits of the carrier image.
This invention uses and extends to the field of steganography the discovery of the class of parametized permutations of a rectangular array of elements (symbols) based on discretized chaotic maps, described in the aforementioned, copending patent application, Ser. No. 08/763,572. A simple software implementation of the new cipher using a desktop computer achieves encryption speeds greater than software implementations of DES that are executed on general purpose computers. Therefore, the invention is a viable and secure alternative to other bulk encryption techniques. It can be used for secure transfer and archival of large quantities of data, such as digital imagery or other large electronic data files.
This invention uses the new class of encryption techniques based on two- and three-dimensional chaotic maps. Chaotic mapping provides excellent security and has many desired cryptographic qualities. It is simple to implement, which results in high encryption rates. A typical software implementation using a 66 MHz Pentium desktop computer achieved a 1 Mb/sec encryption rate. This rate is several orders of magnitude faster than the current software implementation of the public key and bulk encryption methods that utilize higher speed general purpose computers.
Secure transmission and archival of data is of paramount importance to the military, police, and banking industry, and virtually the entire industrial sector in general. Information protection is commonly achieved via encrypting the information using some encryption technique. A large number of powerful encryption schemes, such as DES, RSA, El Gamal, LUCIFER, IDEA, Blowfish (Schneier, B., APPLIED CRYPTOGRAPHY, John Wiley, New York, 1996), etc., have been designed. The security of virtually any encryption technique can be significantly increased if the encrypted information were to look like some other ordinary message (a carrier). The security of the encryption method significantly increases if some useful information can be encrypted and hidden inside some other, innocent-looking message. It is important that an eavesdropper not recognize that some other, secret message is being sent by visually inspecting the carrier message containing the hidden message.
An ideal candidate for hiding secret information is provided by a digitized image. Raw digital images typically contain uncorrelated, thermal Gaussian noise. If a secret message can be masked inside some other image as a random noise, the carrier image with hidden message will not raise a suspicion that some secret information is being sent.
One of the methods for hiding information inside of an ordinary message is to insert "garbage symbols" between the symbols of the secret message. The method requires a mask which can be applied to the text, and which extracts the hidden secret message. However, this method is applicable to text rather than some binary message, such as an image. Also, it is somewhat elaborate and time-consuming to devise an appropriate carrier. Another disadvantage is that the size of the carrier with hidden message significantly exceeds the size of the hidden message, drastically decreasing the efficiency of the whole scheme.
Other methods for hiding information utilize invisible ink, chemical properties of the paper, slight modification of letters, marking letters with pencils, etc. (Schneier, B., APPLIED CRYPTOGRAPHY. John Wiley, New York, 1996). However, since these techniques do not combine encryption with hiding, any person familiar with the principles of the secret embedding can access the secret information.
The scheme described hereinbelow is applicable to both text and binary data files. The expansion factor of the proposed scheme can be made close to 1, if the secret information is a digital image.
To embed a small message of the order of 8 bits or so, an image is scanned until a certain password-dependent message digest hash function returns the required 8-tuple of bits. This has the advantage of absolute secrecy tantamount to one-time pad used in cryptography. The same error distribution and undetectability is guaranteed. Although the scheme satisfies the rigorous requirements of steganographic standards, it is time consuming, has very limited capacity, and is not applicable to image carriers for which only one copy is available.
In "Invisible Communication", by T. Aura, (Proc. of the HUT Seminar on Network Security '95, ESPOO, Finland, November 1995. Telecommunications Software and Multimedia Laboratory, Helsinki University of Technology.), the author suggests changing only a small fraction of the carrier bits (e.g., modifying each hundredth pixel in the carrier by one gray level). Depending on the image noise, these changes are usually compatible with the uncertainties involved with any statistical model of the image.
Before any secret message hiding technique can be considered secure, the carrier image and its statistical properties must be investigated carefully. The noise component may not be uniform within the image, but may depend on the pixel position in the image. For example, pixels corresponding to a bright white color will probably always be saturated at 255, even though the overall model of the noise can be Gaussian with a non-zero variance.
In a black and white image with black pixels corresponding to even gray levels and white pixels corresponding to odd values of gray levels, a large patch of odd pixels, for example, can correspond to pixels saturated at 255 in the original image. Even if only a small fraction of pixels in the image is modified, certain suspicious noise may be introduced into the overflowed patch. This problem with overflow/underflow can of course be avoided by a more careful choice of the carrier image, by preprocessing the carrier, or by instructing the steganographic scheme to avoid the overflowed/underflowed areas.
It is probably impossible to obtain a complete model of the carrier noise, and the search for the perfect steganographic method will probably never be complete. But all good secret hiding schemes must be based on some model of the noise. If it is known that scanned images exhibit larger noise correlations in the horizontal direction and smaller correlations in the vertical direction, while the probability distribution for each pixel (which is neither overflowed nor underflowed) is Gaussian with certain standard deviation, then this evidence is taken into account. The present secret message hiding scheme is adjusted so that the carrier modifications are consistent with the statistical evidence.
An example follows of how to incorporate statistical evidence into the construction of a secret message hiding scheme. Assume that the noise component of pixels with gray levels within the range [L, H] can be modeled with a uniformly valid probability density, f, symmetric around zero. If the secret plain-text message {p.sub.i }.sup.N.sub.i=1 is encrypted, the cipher-text {c.sub.i }.sup.N.sub.i=1 should be a random sequence of ones and zeros. By averaging several scanned versions of the carrier image, a "zero noise" image, Z, is obtained. Using a pseudo-random number generator, we can choose, at random, N pixels in Z with their gray levels in [L, H]. Then, the LSB of those pixels can be modified by the amount of (2b.sub.i -1).vertline..eta..sub.i .vertline., where .eta..sub.i is a random variable with probability distribution f. The remainder of the pixels will be modified by .eta..sub.i. The modifications should be consistent with the statistical model.